package 前K个高频元素;

import javax.jnlp.IntegrationService;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.PriorityQueue;

//堆
public class Solution1 {
    public int[] topKFrequent(int[] nums, int k) {
        //遍历数组，统计各元素出现的次数
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            if(map.containsKey(num)){
                map.put(num,map.get(num)+1);
            }else{
                map.put(num,1);
            }
        }

        PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return map.get(o1) - map.get(o2);
            }
        });

        for (Integer key : map.keySet()) {
            if (queue.size() < k){
                queue.add(k);
            }
            else if(map.get(key) > map.get(queue.peek())){
                queue.remove();
                queue.add(key);
            }
        }

        int[] res = new int[queue.size()];
        while(!queue.isEmpty()){
            for (int i = 0; i < queue.size(); i++) {
                res[i] = queue.remove();
            }
        }

        return res;
    }
}
